package com.algorithms.leetcode.LinkList;

import com.algorithms.leetcode.ListNode;

/**
 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换
 */
public class leetcode_24_swapPairs {

    /**
     * 迭代 看图即可
     *  https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/shou-hua-tu-jie-24-liang-liang-jiao-huan-lian-biao/
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        dummy.next = head;
        while (head != null && head.next != null){
            ListNode next = head.next;
            // 头结点 指向 next的下一结点
            head.next = next.next;
            //反转
            next.next = head;
            prev.next = next;

            //往下移动
            prev =  head;
            head = head.next;
        }
        return dummy.next;
    }

    /**
     * 递归
     * https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/chao-qiang-gifzhu-ni-li-jie-shi-yong-di-gui-fa-qiu/
     * @param head
     * @return
     */
    public ListNode swapPairsV2(ListNode head) {
         if(head == null || head.next == null){
             return head;
         }
         // 这是两两交换 所以 head 和 next是一对儿
         //next之后的子串才要进行递归
         ListNode next = head.next;
         head.next = swapPairsV2(next.next);
         next.next = head;
         return next;
    }
}
